package com.pan.alg.niuke.tree;

import static com.pan.alg.niuke.tree.TreeUtil.generateTree;

/**
 * 输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
 * 在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
 * 平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
 *
 * 数据范围：n \le 100n≤100,树上节点的val值满足 0 \le n \le 10000≤n≤1000
 * 要求：空间复杂度O(1)O(1)，时间复杂度 O(n)O(n)
 */
public class TreeIsBalanced {

    public boolean isBalanced(TreeNode root) {

        int result = isBalancedTree(root,0);

        return result!=-1;
    }


    private int isBalancedTree(TreeNode root, int level) {
        if(root==null){
            return level;
        }
        level++;
        int leftLevel = isBalancedTree(root.left,level);

        int rightLevel = isBalancedTree(root.right,level);
        if(Math.abs(leftLevel-rightLevel)>1){
            return -1;
        }
        return Math.max(leftLevel,rightLevel);
    }

    public static void main(String[] args) {
        int[] tree = new int[]{1,2,3,4,5,6};
        TreeNode head = generateTree(tree);
        TreeIsBalanced treeis = new TreeIsBalanced();
        boolean oo = treeis.isBalanced(head);
        //System.out.println("leftMaxLevel-->"+treeis.leftMaxLevel+",rightMaxLevel-->"+ treeis.rightMaxLevel);
        System.out.println(oo);
    }
}
